package leetcode_题库;

/**
 * Created by IntelliJ IDEA.
 *
 * @ProjectName leetcode
 * @Author Ding
 * @CreateTime 2022/8/24 14:23 星期三
 */
public class _206_反转链表 {

    public static void main(String[] args) {
        ListNode n1 = new ListNode(1);
        ListNode n2 = new ListNode(2);
        ListNode n3 = new ListNode(3);
        ListNode n4 = new ListNode(4);
        ListNode n5 = new ListNode(5);

        n1.next = n2;
        n2.next = n3;
        n3.next = n4;
        n4.next = n5;

        ListNode nn = reverseList(n1);
        while (nn != null) {
            System.err.println(nn.val);
            nn = nn.next;
        }
    }

    /**
     *
     * > 2022/08/24 14:34:51
     * 解答成功:
     * 	执行耗时:0 ms,击败了100.00% 的Java用户
     * 	内存消耗:41.2 MB,击败了55.12% 的Java用户
     * @param head
     * @return
     */
    public static ListNode reverseList(ListNode head) {
        if (head == null || head.next == null){
            //倘若头结点为空或只有一个元素，不需要反转
            return head;
        }
        //建立一个哑结点
        ListNode dumbN = new ListNode(-1);
        //若没走完
        while (head!=null){
            //让dumbN头结点的下一结点指向当前head结点的val并让该节点的下一结点指向原本dumbN的下一结点
            dumbN.next = new ListNode(head.val,dumbN.next);
            //head结点右移
            head = head.next;
        }
        //返回哑结点的后续结点
        return dumbN.next;
    }

    public static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }

}
